package leetcode

import (
	"Algorithms/datastruct"
	"math"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//给你一个二叉树，请你返回其按 层序遍历 得到的节点值。
//（即逐层地，从左到右访问所有节点）。
func levelOrder(root *TreeNode) [][]int {
	var res [][]int
	if root == nil {
		return res
	}
	q := datastruct.Queue{
		Head: &datastruct.Node{
			Data: root,
			Next: nil,
		},
		Tail: nil,
	}
	res = append(res, []int{root.Val})
	//利用队列，每次清空队列得到的是一层，遍历过程再添加进入队列
	for !q.IsEmpty() {
		var treenodes []*TreeNode
		temp := []int{}
		for !q.IsEmpty() {
			treenodes = append(treenodes, q.Dequeue().(*TreeNode))
		}
		for _, tn := range treenodes {
			if tn.Left != nil {
				q.Enqueue(tn.Left)
				temp = append(temp, tn.Left.Val)
			}
			if tn.Right != nil {
				q.Enqueue(tn.Right)
				temp = append(temp, tn.Right.Val)
			}
		}
		if len(temp) != 0 {
			res = append(res, temp)
		}
	}
	return res
}

//1609. 奇偶树
func isEvenOddTree(root *TreeNode) bool {
	q := datastruct.Queue{
		Head: &datastruct.Node{
			Data: root,
			Next: nil,
		},
		Tail: nil,
	}
	index := 0
	//利用队列，每次清空队列得到的是一层，遍历过程再添加进入队列
	for !q.IsEmpty() {
		var treenodes []*TreeNode
		for !q.IsEmpty() {
			treenodes = append(treenodes, q.Dequeue().(*TreeNode))
		}
		for i := range treenodes {
			if index%2 == 0 {
				if i < len(treenodes)-1 && treenodes[i].Val >= treenodes[i+1].Val {
					return false
				}
				if treenodes[i].Val%2 == 0 {
					return false
				}
			} else {
				if i < len(treenodes)-1 && treenodes[i].Val <= treenodes[i+1].Val {
					return false
				}
				if treenodes[i].Val%2 == 1 {
					return false
				}
			}
		}
		index++
		for _, tn := range treenodes {
			if tn.Left != nil {
				q.Enqueue(tn.Left)
			}
			if tn.Right != nil {
				q.Enqueue(tn.Right)
			}
		}
	}
	return true
}

//226. 翻转二叉树
func invertTree(root *TreeNode) *TreeNode {
	if root == nil || (root.Left == nil && root.Right == nil) {
		return root
	}
	left := root.Left
	right := root.Right
	root.Right, root.Left = left, right
	invertTree(root.Right)
	invertTree(root.Left)
	return root
}

//104. 二叉树的最大深度
func maxDepthTree(root *TreeNode) int {
	if root == nil {
		return 0
	}
	max := func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}
	return max(maxDepthTree(root.Right), maxDepthTree(root.Left)) + 1
}

//112. 路径总和
func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}
	var sumTreeNode func(node *TreeNode, sum int) bool
	sumTreeNode = func(node *TreeNode, sum int) bool {
		if node == nil {
			return false
		}
		if node.Left == nil && node.Right == nil {
			if sum+node.Val == targetSum {
				return true
			}
			return false
		}
		return sumTreeNode(node.Left, sum+node.Val) || sumTreeNode(node.Right, sum+node.Val)
	}
	return sumTreeNode(root, 0)
}

//98. 验证二叉搜索树
func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}
	res := make([]int, 0)
	var f func(node *TreeNode)
	f = func(node *TreeNode) {
		if node == nil {
			return
		}
		f(node.Left)
		res = append(res, node.Val)
		f(node.Right)
	}
	f(root)
	for i := 1; i < len(res); i++ {
		if res[i] <= res[i-1] {
			return false
		}
	}
	return true
}

//94. 二叉树的中序遍历，递归
func inorderTraversal(root *TreeNode) []int {
	ans := make([]int, 0)
	var f func(*TreeNode)
	f = func(node *TreeNode) {
		if node == nil {
			return
		}
		f(node.Left)
		ans = append(ans, node.Val)
		f(node.Right)
	}
	f(root)
	return ans
}

//二叉树的中序遍历，迭代，左链入栈
func inorderTraversalIter(root *TreeNode) []int {
	stack := []*TreeNode{}
	res := []int{}
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, root.Val)
		root = root.Right
	}
	return res
}

//144. 二叉树的前序遍历
func preorderTraversal(root *TreeNode) []int {
	stack := []*TreeNode{}
	res := []int{}
	for root != nil || len(stack) > 0 {
		for root != nil {
			res = append(res, root.Val)
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		root = root.Right
	}
	return res
}

//145. 二叉树的后序遍历
func postorderTraversal(root *TreeNode) []int {
	stack := []*TreeNode{}
	res := []int{}
	//用于标记右子树是不是遍历过
	var prev *TreeNode
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		//区别。这里要判断right是不是还有右子树
		if root.Right == nil || root.Right == prev {
			res = append(res, root.Val)
			prev = root
			root = nil
		} else { //右子树不为空，则重新入栈，遍历
			stack = append(stack, root)
			root = root.Right
		}
	}
	return res
}

//114. 二叉树展开为链表，先序，0空间复杂度，倒排
func flatten(root *TreeNode) {
	var last *TreeNode = nil
	var f func(*TreeNode)
	f = func(node *TreeNode) {
		if node == nil {
			return
		}
		f(node.Right)
		f(node.Left)
		node.Right = last
		node.Left = nil
		last = node
	}
	f(root)
}

//105. 从前序与中序遍历序列构造二叉树
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	node := &TreeNode{
		Val:   preorder[0],
		Left:  nil,
		Right: nil,
	}
	for i := 0; i < len(inorder); i++ {
		if preorder[0] == inorder[i] {
			node.Left = buildTree(preorder[1:1+i], inorder[:i])
			node.Right = buildTree(preorder[1+i:], inorder[i+1:])
			return node
		}
	}
	return node
}

//101. 对称二叉树
func isSymmetric(root *TreeNode) bool {
	var f func(left, right *TreeNode) bool
	f = func(left, right *TreeNode) bool {
		if left == nil || right == nil {
			if right == nil && left == nil {
				return true
			}
			return false
		}
		if left.Val != right.Val {
			return false
		}
		return f(left.Left, right.Right) && f(left.Right, right.Left)
	}
	return f(root.Left, root.Right)
}

//96. 不同的二叉搜索树，动态规划？
func numTrees(n int) int {
	var dp = make([]int, n+1)
	dp[0], dp[1] = 1, 1
	var f func(int) int
	f = func(n int) int {
		if dp[n] != 0 {
			return dp[n]
		}
		var sum int
		for i := 0; i < n; i++ {
			//left
			a := f(i)
			//right
			b := f(n - i - 1)
			sum += a * b
		}
		dp[n] = sum
		return sum
	}
	return f(n)
}

//617. 合并二叉树
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	var f func(root1 *TreeNode, root2 *TreeNode) *TreeNode
	f = func(root1 *TreeNode, root2 *TreeNode) *TreeNode {
		if root1 == nil && root2 == nil {
			return nil
		}
		if root1 == nil {
			return root2
		}
		if root2 == nil {
			return root1
		}
		return &TreeNode{
			Val:   root1.Val + root2.Val,
			Left:  f(root1.Left, root2.Left),
			Right: f(root1.Right, root2.Right),
		}
	}
	return f(root1, root2)
}

//124. 二叉树中的最大路径和
func maxPathSum(root *TreeNode) int {
	max := func(a, b, c int) int {
		if a > b {
			if a > c {
				return a
			}
			return c
		}
		if b > c {
			return b
		}
		return c
	}
	m := make(map[*TreeNode]int)
	ans := math.MinInt32
	var f func(node *TreeNode) int
	f = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		if k, ok := m[node]; ok {
			return k
		}
		res := node.Val
		left := f(node.Left)
		right := f(node.Right)
		if left > 0 {
			res += left
		}
		if right > 0 {
			res += right
		}
		if res > ans {
			ans = res
		}
		m[node] = max(node.Val, node.Val+f(node.Left), node.Val+f(node.Right))
		return m[node]
	}
	f(root)
	return ans
}

func convertBST(root *TreeNode) *TreeNode {
	sum := 0
	var f func(node *TreeNode)
	f = func(node *TreeNode) {
		if node == nil {
			return
		}
		f(node.Right)
		sum += node.Val
		node.Val = sum
		f(node.Left)
	}
	f(root)
	return root
}

//543. 二叉树的直径
func diameterOfBinaryTree(root *TreeNode) int {
	ans := 0
	var f func(node *TreeNode) int
	f = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		left := f(node.Left)
		right := f(node.Right)
		ans = max(left+right, ans)
		return max(left, right) + 1
	}
	f(root)
	return ans
}

//437. 路径总和 III
func pathSum(root *TreeNode, targetSum int) int {
	if root == nil {
		return 0
	}
	var found func(*TreeNode, int)
	ans := 0
	found = func(node *TreeNode, sum int) {
		if node == nil {
			return
		}
		if sum+node.Val == targetSum {
			ans++
		}
		found(node.Left, sum+node.Val)
		found(node.Right, sum+node.Val)
	}
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	for len(queue) != 0 {
		temp := queue[len(queue)-1]
		queue = queue[:len(queue)-1]
		if temp.Left != nil {
			queue = append(queue, temp.Left)
		}
		if temp.Right != nil {
			queue = append(queue, temp.Right)
		}
		found(temp, 0)
	}
	return ans
}

//337. 打家劫舍 III
func rob(root *TreeNode) int {
	var f func(*TreeNode, bool) int
	m := make(map[*TreeNode][2]int)
	ans := 0
	f = func(node *TreeNode, b bool) int {
		if node == nil {
			return 0
		}
		var i int
		if !b {
			i = 1
		}
		if v, ok := m[node]; ok {
			if v[i] != 0 {
				return v[i]
			}
		}
		var res, left, right int
		if b {
			res = node.Val + f(node.Left, !b) + f(node.Right, !b)
			if res > ans {
				ans = res
			}
		}
		left = f(node.Left, true)
		right = f(node.Right, true)
		if left+right > ans {
			ans = left + right
		}
		res = max(left+right, res)
		store:=[2]int{}
		store[i]=res
		m[node]=store
		return res
	}
	f(root, true)
	f(root, false)
	return ans
}

//236. 二叉树的最近公共祖先
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	var ans *TreeNode
	var f func(*TreeNode)(bool,bool)
	f= func(node *TreeNode)(bool,bool) {
		if node==nil||ans!=nil{
			return false,false
		}
		var findp,findq bool
		if node.Val==p.Val{
			findp=true
		}
		if node.Val==q.Val{
			findq=true
		}
		findp1,findq1:=f(node.Left)
		findp2,findq2:=f(node.Right)
		findp=findp1||findp2||findp
		findq=findq1||findq2||findq
		if findq&&findp{
			if ans==nil{
				ans=node
			}
		}
		return findp,findq
	}
	f(root)
	return ans
}
